package org.kk.linked;

import org.kk.Common;

/**
 * 合并两个有序链表
 * @author kk
 * @Date 2021/1/23
 */
public class MergeLinked {
    /**
     * 解法一：递归
     * 时间复杂度：O(m+n)，空间复杂度：O(m+n)
     */
    public static Common.ListNode mergeTwoLists1(Common.ListNode list1, Common.ListNode list2) {
        if (list1 == null) {
            return list2;
        }else if(list2 == null){
            return list1;
        }else if(list1.val < list2.val){
            list1.next = mergeTwoLists1(list1.next, list2);
            return list1;
        }else{
            list2.next = mergeTwoLists1(list1, list2.next);
            return list2;
        }
    }

    /**
     * 解法二: 迭代
     * 时间复杂度：O(m+n)，空间复杂度：O(1)
     */
    public static Common.ListNode mergeTwoList2(Common.ListNode listNode1, Common.ListNode listNode2){
        Common.ListNode dummyHead = new Common.ListNode(-1);
        Common.ListNode temp = dummyHead;
        while(listNode1 != null && listNode2 != null){
            if(listNode1.val < listNode2.val){
                temp.next = listNode1;
                listNode1 = listNode1.next;
            }else{
                temp.next = listNode2;
                listNode2 = listNode2.next;
            }
            temp = temp.next;
        }
        temp.next = listNode1 != null ? listNode1 : listNode2;
        return dummyHead.next;
    }
}
